package data_structure.mooc;

import data_structure.helper.ArrayGenerator;
import data_structure.helper.SortingHelper;

//时间复杂度介于o(n^2)和o(nlogn)之间
public class ShellSort {

    private ShellSort() {

    }

    public static <E extends Comparable<E>> void sort(E[] arr) {
        //希尔排序是改良的插入排序，采用分组的方式，对每一组内的元素进行插入排序

        int h = arr.length / 2;

        while (h >= 1) {

            //每一个分组的起始元素
            for (int i = 0; i < h; i++) {

                //对分组里面的元素进行插入排序
                //arr[i,i+h,i+2h,i+3h......]
                //每一个元素之间的间隔为h
                for (int j = h; j < arr.length; j += h) {
                    //记录当前待插入的元素
                    E temp = arr[j];
                    //插入的位置
                    int k = j;
                    while (k - h >= 0 && arr[k - h].compareTo (temp) > 0) {
                        arr[k] = arr[k - h];
                        k-=h;
                    }
                    arr[k] = temp;
                }
            }
            h /= 2;
        }
    }

    public static void main(String[] args) {
        Integer []arr= ArrayGenerator.generateNormalArray (100000,10000);
        SortingHelper.testSorting (arr,"ShellSort");
    }
}
